// $Id: bloomfilterquadstate.cpp 63 2004-10-22 14:33:20Z jonas $
#include "bloomfilterquadstate.h"
#include "file.h"
#include <memory.h>
#include <strings.h>
#include <math.h>
using namespace std;

BloomFilterQuadState::BloomFilterQuadState()
{
	int size = (BloomFilterQuadStateCount*2-1)/8 + 1;

	// Reserve space for all bits
	bits = new unsigned char[size];

	// Unset all bits
	bzero(bits, size);
}

/**
 * Copy constructor. Make an identical copy of a BloomFilterQuadState object.
 *
 * @param bloomFilter The object to copy from.
 */
BloomFilterQuadState::BloomFilterQuadState(const BloomFilterQuadState &bloomFilter)
{
	int size = (BloomFilterQuadStateCount*2-1)/8 + 1;
	bits = new unsigned char[size];
	memcpy(bits, bloomFilter.bits, size);
}

/**
 * Clean up allocated memory.
 */
BloomFilterQuadState::~BloomFilterQuadState()
{
	delete[] bits;
}

/**
 * Returns a pointer to a copy of the input. This is equal to calling new, and the caller MUST handle delete apropriately!
 * @return A new object identical to this object
 */
BloomFilter *BloomFilterQuadState::newCopy()
{
	//return new BloomFilterQuadState(*((BloomFilterQuadState *)fileMesh));
	return new BloomFilterQuadState(*this);
}

/**
 * Estimates a distance from the hash using a stored file mesh.
 *
 * @param hash The hash to find out the distance to.
 * @returns The estimated distance.
 */
unsigned int BloomFilterQuadState::calcDistance(unsigned int hash)
{
	int i=0;
	int index = getIndex(hash);
	unsigned char valOne, valTwo, value;

	// Calc how large keyspace each bit in the filter represents
	int BloomFilterQuadStateWidth = RAND_MAX/BloomFilterQuadStateCount;

	// Find nearest set bit
	while(index+i<BloomFilterQuadStateCount || index-i>=0){
		if((index+i<BloomFilterQuadStateCount && (valOne = getQuad(index+i))) || (index-i>=0 && (valTwo = getQuad(index-i)))){
			if(valOne>valTwo){
				value = valOne;
			}
			else{
				value = valTwo;
			}
//cout << "Bloom says:\t" << (unsigned int) ((i*BloomFilterQuadStateWidth)/((value+1)*0.5)) << "\t" << i << "\t" << (int)value << endl;	// DEBUG
			return (unsigned int) ((i*BloomFilterQuadStateWidth)/((value+1)*0.5));	/// @todo Evaluate different weights....
		}
		i++;
	}
	return RAND_MAX;
}

/**
 * Update the filter by setting the apropriate value for the supplied hash.
 *
 * @param hash The hash to insert into the filter
 */
void BloomFilterQuadState::update(unsigned int hash, map<File *, StoredFile *> &fileStore)
{
	/// @todo Check if this can be done more efficiently than a call to rebuild...
	rebuild(fileStore);
}

/**
 * Since we cannot update the filter correctly if a hash is removed from it we
 * need to rebuild it if it happens. This method inserts all hashes from the
 * supplied file store into the filter.
 *
 * @param fileStore The file store to insert into the filter.
 */
void BloomFilterQuadState::rebuild(map<File *, StoredFile *> &fileStore)
{
	// Calculate how many files there are in each bloom filter partition
	unsigned char countingBloom[BloomFilterQuadStateCount] = {0};
	for (map<File *, StoredFile *>::iterator file=fileStore.begin(); file!=fileStore.end(); file++) {
		if(countingBloom[getIndex((*file).first->m_hash)]++ > 253){
			for(int i=0;i<BloomFilterQuadStateCount;i++){
				// Security run: If any value in the array maxes out, half the whole array, but make sure that we not loose any values above zero
				if(countingBloom[i]==1){
					countingBloom[i]++;
				}
				countingBloom[i] /= 2;
			}
		}
	}

	// Find max and average count
	int maxCount = 0, averageSetCount = 0, setCount = 0;
	for(int i=0;i<BloomFilterQuadStateCount;i++){
		if(countingBloom[i]>maxCount){
			maxCount = countingBloom[i];
		}
		if(countingBloom[i]>0){
			averageSetCount+=countingBloom[i];
			setCount++;
		}
//if(maxCount > 1 && countingBloom[i]>0){cout << (int)countingBloom[i] << ",";}	// DEBUG
	}
//if(maxCount > 1){cout << endl;}	// DEBUG
	averageSetCount /= setCount;

	// Reset all values to zero
	bzero(bits, ((BloomFilterQuadStateCount*2-1)/8 + 1));

	// Map all stored files to the filter
	int index;
	for (map<File *, StoredFile *>::iterator file=fileStore.begin(); file!=fileStore.end(); file++) {
		index = getIndex((*file).first->m_hash);
		if(countingBloom[index]==0){
			setQuad(index, 0);
		}
		else if(countingBloom[index]==maxCount){
			setQuad(index, 3);
		}
		else if(countingBloom[index]>averageSetCount){
			setQuad(index, 2);
		}
		else{
			setQuad(index, 1);
		}
	}
}

/**
 * Get the state of a value in the filter.
 *
 * @param index The index of the value to retrieve status on.
 * @returns Returns the value
 */
unsigned char BloomFilterQuadState::getQuad(int index)
{
	assert(index>=0 && index<BloomFilterQuadStateCount);

	// Mask out and return bit value
	return (unsigned char) ((bits[(index*2)/8] & ((unsigned char) ::pow(2, (index*2)%8))*3) >> (index*2)%8);
}

/**
 * Set a value in the filter to a specified value.
 *
 * @param index The index of the value to manipulate.
 * @param value The value to set.
 */
void BloomFilterQuadState::setQuad(int index, unsigned char value)
{
	assert(index>=0 && index<BloomFilterQuadStateCount);
	assert(value < 4);

	// Do we need to change a bit?
	if (getQuad(index) != value) {
		/*if (value) {
			bits[index/8] |= (unsigned char) pow(2, 7-(index%8));
		} else {
			bits[index/8] &= (unsigned char) (255 - pow(2, 7-(index%8)));
		}*/

		// Clear the two byte position
		bits[(index*2)/8] &= 255-((unsigned char) ::pow(2, (index*2)%8))*3;

		// Set the new value
		bits[(index*2)/8] |= (value << (index*2)%8);
	}
}

/**
 * Get the index position in the filter for a specified value
 *
 * @param value The value that should be used to get the index
 * @return index The index of the value
 */
int BloomFilterQuadState::getIndex(int value)
{
	return (int) ((value/(double)RAND_MAX)*BloomFilterQuadStateCount);
}
